package com.xingjiejian.leetcode.easy;

/**
 * 14. 最长公共前缀
 * <p>
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 * 示例 1:
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 示例 2:
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 * 说明:
 * 所有输入只包含小写字母 a-z 。
 *
 * @author XingJiejian
 * @date 2019/5/9 0009
 */
public class LongestCommonPrefix {
    /**
     * 算法分析：水平扫描法
     * 从前往后枚举字符串的每一列，先比较每个字符串相同列上的字符（即不同字符串相同下标的字符）
     * 然后再进行对下一列的比较。
     * <p>
     * 复杂度分析
     * 时间复杂度：O(S)，S 是所有字符串中字符数量的总和。
     * 最坏情况下，输入数据为n个长度为m的相同字符串，算法会进行 S = m*n 次比较。
     * 可以看到最坏情况下，本算法的效率与算法一相同，但是最好的情况下，算法只需要进行 n*minLen次比较，
     * 其中 minLen是数组中最短字符串的长度。
     * 空间复杂度：O(1)，我们只需要使用常数级别的额外空间。
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        //依次取第一个字符串的前缀，匹配后面每一个字符，出现
        for (int i = 0; i < strs[0].length(); i++) {
            for (int j = 1; j < strs.length; j++) {
                char ch = strs[0].charAt(i);
                // 如果前缀长度超出后续字符串长度，或者对应下标字符不匹配
                if (i == strs[j].length() || strs[j].charAt(i) != ch) {
                    // 返回上一个匹配前缀，substring返回[0,i);
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    /**
     * 水平扫描法
     * 思路：
     * 首先，我们将描述一种查找一组字符串的最长公共前缀 LCP(S1…Sn)的简单方法。
     * 我们将会用到这样的结论：
     * LCP(S1...Sn) = LCP(LCP(LCP(S1, S2),S3), ... Sn)
     * 算法
     * 为了运用这种思想，算法要依次遍历字符串[S1...Sn],当遍历到第i个字符串的时候，找到最长公共前缀
     * LCP(S1...Si)，当LCP(S1...Si)是一个空串的时候，算法就结束了。 否则，在执行了n次遍历之后，
     * 算法就会返回最终答案LCP(S1...Sn)
     *
     * 复杂度和上一种一样
     * @param strs
     * @return
     */
    public String longestCommonPrefix1(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }
}
